/**
 * 
 */
package leetCode;

/**
 * @author zhong
 *
 */
public class SplitArrayWithSameAverage {
	public boolean splitArraySameAverage(int[] A) {
		int n = A.length;
		int totalSum = 0;
		for (int i = 0; i < A.length; i++) {
			totalSum += A[i];
		}
		// double avg=(double)sum/n;
		// TODO 研究怎样设置for循环
		boolean dp[][] = new boolean[totalSum + 1][n + 1];
		dp[0][0] = true;
		for (int i = 0; i < n; i++) {
			for (int j = totalSum - A[i]; j >= 0; j--) {
				for (int k = 0; k < n - 1; k++) {
					if (dp[j][k]) {
						dp[j + A[i]][k + 1] = true;
						if ((j + A[i]) * n == (k + 1) * totalSum) {
							return true;
						}
					}
				}
			}
		}
		return false;
	}

	/**
	 * @param args
	 */
	public static void main(String[] args) {
		int[] A = { 17, 5, 5, 1, 14, 10, 13, 1, 6 };
		System.out.println(new SplitArrayWithSameAverage().splitArraySameAverage(A));

	}

}
